package SwordFingerOffer;

import java.util.Stack;

public class Q30_MinStack {
    //本类代码能跑 但性能过差  参考LeetCode答题记录
    //主栈
    Stack<Integer> stack;
    //辅助栈
    Stack<Integer> minStack;
    Stack<Integer> help;

    //最小栈
    public Q30_MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
        this.help = new Stack<>();
    }

    public void push(int x) {
        stack.add(x);
        if (minStack.empty()){
            minStack.add(x);
        }else {
            while (!minStack.isEmpty() && minStack.peek() < x){
                help.add(minStack.pop());
            }
            //不管怎样，总要进去的，因为要记录状态
            minStack.add(x);
            //不管怎样 总要恢复的
            while (!help.isEmpty()){
                minStack.add(help.pop());
            }

        }
    }

    public void pop() {
        Integer pop = stack.pop();
        while (!minStack.isEmpty()){
            Integer pop1 = minStack.pop();
            if (pop1.equals(pop)){
                break;
            }
            help.add(pop1);
        }
        while (!help.isEmpty()){
            minStack.add(help.pop());
        }
    }

    public int top() {
        return stack.isEmpty()? -10086 : stack.peek();
    }

    //返回最小元素
    //时空复杂度都算O(1)
    public int min() {
        if (!minStack.empty()){
            return minStack.peek();
        }
        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        Q30_MinStack fun = new Q30_MinStack();
        fun.push(2);
        fun.push(0);
        fun.push(-3);
        System.out.println(fun.min());
        fun.pop();
        System.out.println(fun.top());
        System.out.println(fun.min());
    }
}
